import java.util.Random;


public class MaxSubSum {

    static private int seqStart = 0;
    static private int seqEnd = -1;

    /**
     * Cubic maximum contiguous subsequence sum algorithm.
     * seqStart and seqEnd represent the actual best sequence.
     */
    public static int maxSubSum3( int [ ] a )
    {
        int maxSum = 0;

        for( int i = 0; i < a.length; i++ )
            for( int j = i; j < a.length; j++ )
            {
                int thisSum = 0;

                for( int k = i; k <= j; k++ )
                    thisSum += a[ k ];

                if( thisSum > maxSum )
                {
                    maxSum   = thisSum;
                    seqStart = i;
                    seqEnd   = j;
                }
            }

        return maxSum;
    }


    /**
     * Quadratic maximum contiguous subsequence sum algorithm.
     * seqStart and seqEnd represent the actual best sequence.
     */
    public static int maxSubSum2( int [ ] a )
    {
        int maxSum = 0;

        for( int i = 0; i < a.length; i++ )
        {
            int thisSum = 0;
            for( int j = i; j < a.length; j++ )
            {
                thisSum += a[ j ];

                if( thisSum > maxSum )
                {
                    maxSum = thisSum;
                    seqStart = i;
                    seqEnd   = j;
                }
            }
        }

        return maxSum;
    }

    /**
     * Linear-time maximum contiguous subsequence sum algorithm.
     * seqStart and seqEnd represent the actual best sequence.
     */
    public static int maxSubSum1( int [ ] a )
    {
        int maxSum = 0;
        int thisSum = 0;

        for( int i = 0, j = 0; j < a.length; j++ )
        {
            thisSum += a[ j ];

            if( thisSum > maxSum )
            {
                maxSum = thisSum;
                seqStart = i;
                seqEnd   = j;
            }
            else if( thisSum < 0 )
            {
                i = j + 1;
                thisSum = 0;
            }
        }

        return maxSum;
    }

    public static void main(String[] args) {
        int[] a = new int[Integer.parseInt(args[0])];
        Random rand = new Random();

        for (int i=0; i < a.length; ++i) {
            a[i] = rand.nextInt() % 10;
        }

        int maxSum;

        maxSum = maxSubSum1( a );
        System.out.println( "\nMax sum is " + maxSum + "; it goes"
                       + " from " + seqStart + " to " + seqEnd );
        System.out.flush();

        maxSum = maxSubSum2( a );
        System.out.println( "\nMax sum is " + maxSum + "; it goes"
                       + " from " + seqStart + " to " + seqEnd );
        System.out.flush();

        maxSum = maxSubSum3( a );
        System.out.println( "\nMax sum is " + maxSum + "; it goes"
                       + " from " + seqStart + " to " + seqEnd );
        System.out.flush();
    }
}